import java.util.Random;

public class test_quickSort {
    // https://leetcode.cn/problems/sort-colors/
    public void sortColors(int[] nums) {
        int left=-1;
        int right=nums.length;
        int i=0;
        while(i<right) {
            if(nums[i]==0) {
                swap(nums,++left,i++);
            } else if(nums[i]==1) {
                i++;
            } else {
                swap(nums,--right,i);
            }
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

    // https://leetcode.cn/problems/sort-an-array/
    public int[] sortArray(int[] nums) {
        qsort(nums,0,nums.length-1);
        return nums;
    }
    public void qsort(int[] nums,int l,int r) {
        if(l>=r) return;
        int key=nums[new Random().nextInt(r-l+1)+l];
        int left=l-1;
        int right=r+1;
        int i=l;
        while(i<right) {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }
        // 此时数组被分成了[0,left],[left+1,right-1],[right,r]这三部分
        //接下来仅需对[0,left],[right,r]这两部分进行排序即可
        qsort(nums,l,left);
        qsort(nums,right,r);
    }

    // 快速选择排序(数组中第k大元素) https://leetcode.cn/problems/kth-largest-element-in-an-array/
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }
    public int qsort(int[] nums,int l,int r,int k) {
        if(l==r) return nums[l];
        // 1. 随机选择一个基准元素
        int key=nums[new Random().nextInt(r-l+1)+l];
        // 2. 根据基准元素,将数组分成三块
        int left=l-1,right=r+1,i=l;
        while(i<right) {
            if(nums[i]<key) {
                swap(nums,++left,i++);
            } else if(nums[i]==key) i++;
            else {
                swap(nums,--right,i);
            }
        }
        // 3. 分类讨论 [l,left],[left+1,right-1],[right,r]
        int b=right-left-1,c=r-right+1;
        if(c>=k) return qsort(nums,right,r,k);
        else if(b+c>=k) return key;
        else return qsort(nums,l,left,k-b-c);
    }

    // https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
    /*
    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock,0,stock.length-1,cnt);
        int[] ret=new int[cnt];
        for(int i=0;i<cnt;i++) {
            ret[i]=stock[i];
        }
        return ret;
    }
    public void qsort(int[] nums,int l,int r,int k) {
        if(l>=r) return;
        int left=l-1,right=r+1,i=l;
        int key=nums[new Random().nextInt(r-l+1)+l];
        while(i<right) {
            if(nums[i]<key) {
                swap(nums,++left,i++);
            }else if(nums[i]==key) i++;
            else {
                swap(nums,--right,i);
            }
        }
        int a=left-l+1,b=right-1-left;
        if(a>k) {
            qsort(nums,l,left,k);
        } else if(a+b>=k) return;
        else {
            qsort(nums,right,r,k-a-b);
        }
    }
    */
}
